package com.likou.second_challenge;

import com.likou.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

public class q230 {

    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        TreeNode p = root;
        int mark = 0;
        int ans = 0;

        while (p != null || !deque.isEmpty()) {
            while (p != null) {
                deque.push(p);
                p = p.left;
            }

            TreeNode poll = deque.poll();
            mark++;
            if (mark == k) {
                ans = poll.val;
                break;
            }
            p = poll.right;
        }

        return ans;
    }

}
